package puzzle.projecteuler.p100;

import astudy.util.AdvMath;

public class Problem091 {

	/**
	 * suppose 0<=x1,x2,y1,y2<=m
	 * if O is Right angle, it is easy. this number of m^2。  
	 * if (x2, y2) is Right angle, then x1x2 + y1y2 = x2^2 + y2^2
	 * this equation can be solved easily:
	 *    x2 = a*d, y2 = b*d, gcd(a,b)=1, c = (a^2 + b^2)*d   
	 * => a*x1 + b*y1 = c
	 * => x1 = a*d - b*k
	 *    y1 = b*d + a*k
	 *    k is integer, d = gcd(x2, y2), a = x2/d, b = y2/d
	 * => 0<= ad-bk <=m, 0<= bd+ak <=m
	 * => (ad-m)/b<= k <= ad/b, -bd/a <= k <= (m-bd)/a 
	 * @param args
	 */
	public static void main(String[] args) {
		
		int m = 50;
		int c = m*m;	//O is Right angle
		for (int a = 0; a <= m; a ++) {
			for (int b = 0; b <= m; b ++) {
				if (a == 0 && b == 0) {
					continue;
				} else {
					//NOTE: 
					//减1，是因为要减去x=a, y=b这组解
					//乘2，是因为P1与P2对称
					c += (count(a, b, m)-1);
				}
			}
		}
		System.out.println(c);
	}
	
	/**
	 * number of solutions: a*x + b*y = a^2 + b^2, 0<=x, y<=m
	 * 其中0<=a,b<=m
	 * 
	 * 
	 * @return
	 */
	public static int count(int a, int b, int m) {

		if (a == 0 || b == 0) {
			return m+1;
		} else {
			int d = (int)AdvMath.gcd(a, b);
			a = a/d;
			b = b/d;
			int u = Math.max((a*d-m)/b, -b*d/a);
			int v = Math.min(a*d/b, (m-b*d)/a);
			return v-u+1;
		}
	}

}
